package Array.easy;


/**
 * 1. 问题描述
 *      平面上有n个点，点的位置用整数坐标表示points[i] = [xi, yi]。
 *      请你计算访问所有这些点需要的最小时间（以秒为单位）。
 *      你可以按照下面的规则在平面上移动：
 *      每一秒沿水平或者竖直方向移动一个单位长度，或者跨过对角线（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
 *      必须按照数组中出现的顺序来访问这些点。
 *
 * 2. 算法分析
 *      1. 线性遍历
 *          我们需要判断前后两个点之间的位置关系，然后移动即可，下面的代码思路简单，但是时间复杂度非常高
 *
 *      对上述代码进行优化
 *
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 访问所有点的最小时间 {
    public static void main(String[] args) {
        int[][] points = {{1,1},{3,4},{-1,0}};
        System.out.println(minTimeToVisitAllPoints(points));
    }

    /**
     *
     * @param points
     * @return
     */
    public static int minTimeToVisitAllPoints(int[][] points) {
        int pointCounts = points.length; // 所有点的数量
        int ans = 0;
        for(int i = 0; i < pointCounts - 1; i++) {
            int[] point1 = points[i]; // 第一个点
            int[] point2 = points[i+1]; // 第二个点
            if(point1[0] == point2[0]) {
                // 当前两个点在一个数轴上
                ans += (point1[1] > point2[1]) ? point1[1] - point2[1] : point2[1] - point1[1];
            } else if(point1[1] == point2[1]) {
                // 当前两个点在一个横轴上
                ans += (point1[0] > point2[0]) ? point1[0] - point2[0] : point2[0] - point1[0];
            } else {
                // 不在水平或者竖直的方向上
                if(point1[0] < point2[0] && point1[1] < point2[1]) {
                    // 第二个点在第一个点的↑→
                    int x = point1[0];
                    int y = point1[1];
                    while(x < point2[0] && y < point2[1]) {
                        x ++;
                        y ++;
                    }
                    ans += (x - point1[0]);
                    ans += (x == point2[0]) ? point2[1] - y : point2[0] - x;
                } else if(point1[0] < point2[0] && point1[1] > point2[1]) {
                    //  第二个点在第一个点的↓→
                    int x = point1[0];
                    int y = point1[1];
                    while(x < point2[0] && y > point2[1]) {
                        x ++;
                        y --;
                    }
                    ans += (x - point1[0]);
                    ans += (x == point2[0]) ? y - point2[1] : point2[0] - x;
                } else if(point1[0] > point2[0] && point1[1] < point2[1]) {
                    // 第二个点在第一个点的←↑
                    int x = point1[0];
                    int y = point1[1];
                    while(x > point2[0] && y < point2[1]) {
                        x --;
                        y ++;
                    }
                    ans += (y - point1[1]);
                    ans += (x == point2[0]) ? point2[1] - y : x - point2[0];
                } else if(point1[0] > point2[0] && point1[1] > point2[1]) {
                    // 第一个点在第二个点的←↓
                    int x = point1[0];
                    int y = point1[1];
                    while(x > point2[0] && y > point2[1]) {
                        x --;
                        y --;
                    }
                    ans += (point1[0] - x);
                    ans += (x == point2[0]) ? y - point2[1] : x - point2[0];
                }
            }
        }
        return ans;
    }

    /**
     * 优化算法
     * 我们无须将点之间的距离求出来，观察如果才能使得两点之间的距离最短(整点位置)
     * 我们得出下述公式：
     *      a = (x1,y1) b = (x2,y2)
     *      min d(a,b) = max(abs(x1-x2),abs(y1-y2));
     *  然后线性求和即可
     * @param points
     * @return
     */
    public static int minTimeToVisitAllPoints2(int[][] points) {
        int ans = 0;
        for(int i = 0; i < points.length - 1; i++) {
            int temp1 = Math.abs(points[i][0]-points[i+1][0]);
            int temp2 = Math.abs(points[i][1]-points[i+1][1]);
            ans += Math.max(temp1,temp2);
        }
        return ans;
    }
}
